package com.leetcode.binary_search;

/**
 * @author Dennis Li
 * @date 2020/11/4 20:32
 */
public class SearchRange_33 {

    public static void main(String[] args) {
        SearchRange_33 solution = new SearchRange_33();
        int[] nums = {3, 1};
        System.out.println(solution.search(nums, 3));
    }

    public int search(int[] nums, int target) {
        int len = nums.length;
        int i = 0, j = len - 1, left = nums[i], right = nums[j];
        while (i <= j) {
            int mid = i + (j - i) / 2;
            if (nums[mid] == target)
                return mid;

            if (target >= left && nums[mid] < left) {
                // 在左部分，由于此时已经包括了target，所以要求INF部分严格不包括left，否则可能排除掉target
                nums[mid] = Integer.MAX_VALUE;
            } else if (target < left && nums[mid] >= right) {
                // 在右部分，由于此时没有包括left，target
                nums[mid] = Integer.MIN_VALUE;
            }

            if (nums[mid] > target) {
                j = mid - 1;
            } else {
                i = mid + 1;
            }
        }
        return -1;
    }

}
